package me.helllp.bootman.common.utils;

import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

import me.helllp.bootman.common.utils.ConsistentHash.Node;


/**
 * 一致性hash
 *
 * @param <Node>
 */
@SuppressWarnings("hiding")
public class ConsistentHash<Node> {
    public static class Node{  
        String name;  
        String ip;  
        public Node(String name,String ip) {  
            this.name = name;  
            this.ip = ip;  
        }  
        @Override  
        public String toString() {  
            return this.name+"-"+this.ip;  
        }  
    }  
    
    // 	虚拟节点到真实节点的映射
    static private TreeMap<Long, Node> nodes;
    
    //	key到真实节点的映射
//    static private TreeMap<Long,Node> treeKey;
    
    // 	真实机器节点
    private List<Node> shards;
    
    // 	每个机器节点关联的虚拟节点个数
    private final int NODE_NUM = 100;   
      
    public ConsistentHash(List<Node> shards) {  
        super();  
        this.shards = shards;  
        //	初始化生成Hash环
        init();  
    }  
    
    /**
     * 初始化一致性Hash环
     */
    private void init() {  
        nodes = new TreeMap<Long, Node>();  
  
        for (int i = 0; i != shards.size(); ++i) { // 每个真实机器节点都需要关联虚拟节点  
            final Node shardInfo = shards.get(i);  
  
            for (int n = 0; n < NODE_NUM; n++)  
                // 一个真实机器节点关联NODE_NUM个虚拟节点  
                nodes.put(hash("SHARD-" + shardInfo.name + "-NODE-" + n), shardInfo);  
        }  
    }  

    /**
     * 增加一个主机 
     * @param s
     */
    public void addS(Node s) {  
        System.out.println("增加主机"+s+"的变化：");  
        for (int n = 0; n < NODE_NUM; n++){
        	nodes.put(hash("SHARD-" + s.name + "-NODE-" + n), s);
        }
    }  
      
    /**
     * 删除真实的节点
     * 
     * @param s
     */
    public void deleteS(Node s){  
        if(s==null){  
            return;  
        }  

        for(int i=0;i<NODE_NUM;i++){  
            //定位s节点的第i的虚拟节点的位置  
            SortedMap<Long, Node> tail = nodes.tailMap(hash("SHARD-" + s.name + "-NODE-" + i));  
            SortedMap<Long,Node>  head = nodes.headMap(hash("SHARD-" + s.name + "-NODE-" + i));  
              
            if(head.size()==0){  
                tail.remove(tail.firstKey());  
                nodes.remove(tail.firstKey());//从nodes中删除s节点的第i个虚拟节点  
            }else{  
                tail.remove(tail.firstKey());  
            }  
        }  
    }  
  
    /**
     * 获取映射Key的真实节点
     * 
     * @param key
     */
    public Node keyToNode(String key){  
        SortedMap<Long, Node> tail = nodes.tailMap(hash(key)); // 沿环的顺时针找到一个虚拟节点  
        if (tail.size() == 0) {  
            return null;  
        }  
        
        return tail.get(tail.firstKey());
    }  
      
    /** 
     *  MurMurHash算法，是非加密HASH算法，性能很高， 
     *  比传统的CRC32,MD5，SHA-1（这两个算法都是加密HASH算法，复杂度本身就很高，带来的性能上的损害也不可避免） 
     *  等HASH算法要快很多，而且据说这个算法的碰撞率很低. 
     *  http://murmurhash.googlepages.com/ 
     */  
    private static Long hash(String key) {  
          
        ByteBuffer buf = ByteBuffer.wrap(key.getBytes());  
        int seed = 0x1234ABCD;  
          
        ByteOrder byteOrder = buf.order();  
        buf.order(ByteOrder.LITTLE_ENDIAN);  
  
        long m = 0xc6a4a7935bd1e995L;  
        int r = 47;  
  
        long h = seed ^ (buf.remaining() * m);  
  
        long k;  
        while (buf.remaining() >= 8) {  
            k = buf.getLong();  
  
            k *= m;  
            k ^= k >>> r;  
            k *= m;  
  
            h ^= k;  
            h *= m;  
        }  
  
        if (buf.remaining() > 0) {  
            ByteBuffer finish = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN);  
            finish.put(buf).rewind();  
            h ^= finish.getLong();  
            h *= m;  
        }  
  
        h ^= h >>> r;  
        h *= m;  
        h ^= h >>> r;  
  
        buf.order(byteOrder);  
        return h;  
    }
    
}
